package no26;


/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/17 14:11
 * 树的子结构
 */
public class Solution {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 空树表示任意一个树的子结构
        if (A == null || B == null) {
            return false;
        }
        // 先找到起始比较位置
        boolean result = false; // 记录结果
        if (A.val == B.val) {
            // 找到了起始位置
            result = isSameTree(A, B); // 判定指定的两个树, 各自的左右子树是否相等
        }
        // 如果没有找到, 则依次从左右子树里找
        if (result != true) {
            result = isSubStructure(A.left, B);
        }
        if (result != true) {
            result = isSubStructure(A.right, B);
        }
        // 返回结果
        return result;
    }

    // 判定给定的两个二叉树, 各自左右子树是否相等
    private boolean isSameTree(TreeNode A, TreeNode B) {
        // 由于是判断 B 是否为 A 的子结构, 如果 B 遍历完了, 说明 B 是 A 的子结构
        if (B == null) {
            return true;
        }
        // 如果 A 先遍历完, 则说明 B 不是 A 的子结构
        if (A == null) {
            return false;
        }
        // 如果 A 和 B 当前位置的值不同, 也可以排除
        if (A.val != B.val) {
            return false;
        }
        // 继续判断各自的左子树右子树是否相等
        return isSameTree(A.left, B.left) && isSameTree(A.right, B.right);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
